\documentclass[a4paper,twoside,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[pdftex]{graphicx, color}
\usepackage{float}
\usepackage{url}
%\usepackage[tmargin=2.5cm, bmargin=3cm,lmargin=2.5cm, rmargin=2cm]{geometry}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{insa}

%opening
\title{
\Huge{Mini-projet de C++}\\
\Large{Génération automatique de grilles de mots croisés.}
}
\author{
Vincent CHABOT, Nguyen DIEP, Paul MYCEK\\
\normalsize{Institut National des Sciences Appliquées de Rouen,}\\
\normalsize{département Génie Mathématique, 4\up{ème} année.}
}
\date{}

\definecolor{colKeys}{rgb}{0,0.39,0}
\definecolor{colIdentifier}{rgb}{0,0,0}
\definecolor{colComments}{rgb}{0,0,1}
\definecolor{colString}{rgb}{0.6,0.1,0.1}
\definecolor{ok}{rgb}{0.53,1,0.44}
\definecolor{pasok}{rgb}{1,0.44,0.44}
\definecolor{gris}{rgb}{0.86,0.86,0.86}

\lstdefinelanguage{xml}{
extendedchars=true,
morekeywords=[1]{
	Grille,
	Details,
Contenu,
Mot,
Libelle,
Definition},
morekeywords=[2]{
	hauteur,
	longueur,
nbCasesNoires,
nbMotsH,
nbMotsV,
ligne,
colonne,
vertical},
keywordstyle=[1]\sffamily\bfseries\color{colKeys},
keywordstyle=[2]\sffamily\bfseries\color{colComments},
moredelim=[s][\color{colString}]{"}{"},
morecomment=[l]{//},
numbers=none,
sensitive=false,
tabsize=2,
basicstyle=\sffamily\script,
}

\lstset{
language=xml,
basicstyle=\ttfamily\footnotesize,
tabsize=2,
alsolanguage=xml
}

\begin{document}
\pageDeGarde{Mini-projet de C++}{Génération automatique de grilles de mots croisés.}{Génie Mathématique 4\up{ème} année}{CHABOT Vincent, DIEP Nguyen et MYCEK Paul}

\newpage
\tableofcontents\thispagestyle{empty}

\newpage
\section*{Introduction}
\addcontentsline{toc}{section}{Introduction}

\newpage
\section*{Notations}
\addcontentsline{toc}{section}{Notations}

\begin{center}
% use packages: array
\begin{tabular}{ll}
$G$ & Grille de mots croisés. \\ 
$l_{G}$ & Longueur de $G$, ie nombre de cases composant une ligne. \\ 
$h_{G}$ & Hauteur de $G$, ie nombre de cases composant une colonne. \\
$l(x)$ & Longueur du mot $x$, ie nombre de lettres composant ce mot. \\
\end{tabular}
\end{center}

\newpage
\section{Analyse des besoins}
\subsection{Ce que doit faire le programme}
Le but de notre projet sera de générer automatiquement des grilles de mots croisés en langue française à l'aide d'une importante base de donnée.

Toutefois, on pourrait imaginer utiliser des bases de données dans des langues différentes (par exemple l'Anglais), ou regroupant des mots d'un domaine spécifique (par exemple la médecine).
Notre système devra, dans la mesure du possible, être portable et donc pouvoir s'adapter à différentes bases de données. 

La grille de mots croisés sera générée automatiquement sous certaines contraintes décrites plus bas, soit directement en mode console, soit dans un fichier texte dont l'utilisateur aura spécifié le nom.

Enfin, nous développerons éventuellement le module de jeu. Un utilisateur pourra essayer de résoudre une grille de mots croisés préalablement générée. Il faudra donc prévoir deux utilisations différentes : l'utilisation en tant que \textbf{créateur} de grille, et l'utilisation en tant que \textbf{joueur}. Ceci pourra être mis en place aisément par la programmation d'un menu en début de programme.

\subsection{Ce que ne fera pas le programme}
Notre programme ne générera pas la liste des définitions relatives aux mots composant la grille. Ce sera à la charge de l'utilisateur de trouver celles-ci pour pouvoir faire profiter d'autres personnes du jeu.

Néanmoins, nous développerons un module permettant à l'utilisateur d'entrer les définitions qu'il souhaite une fois la grille de mots générée.

\subsection{Grandes fonctionnalités}
L'utilisateur devra pouvoir choisir un certain nombre de paramètres :
\paragraph{Les dimensions de la grille.} L'utilisateur choisira la longueur $l_{G}$ et la hauteur $h_{G}$ de la grille $G$. On imposera les contraintes suivantes :
$$\left\lbrace
% use packages: array
\begin{array}{l} 
5 \leq l_{G} \leq 50\\ 
5 \leq h_{G} \leq 50
\end{array}
\right.$$
En pratique, les dimensions seront bien entendu généralement comprises entre 8 et 15, mais il pourra être intéressant d'étudier les solutions pour des grilles exagérément petites ou grandes.

\paragraph{Des contraintes sur les mots.} L'utilisateur pourra également imposer un nombre maximal de mots courts\footnotemark[1]. Eventuellement, on peut imaginer d'autres contraintes facultatives :
\begin{itemize}
\item Un nombre maximal de mots longs\footnotemark[1] ;
\item une longueur de mots moyenne qui devra être respectée sur l'ensemble de la grille ;
\item une longueur de mots minimale et une longueur de mots maximale ;
\end{itemize}

\paragraph{N.B.} Bien entendu, il ne pourra exister de mots de longueur 1.

\bigskip
En plus de ces paramètres variables, nous imposerons un certain nombre de paramètres fixes :
\begin{itemize}
 \item Une proportion de cases noires à respecter sur l'ensemble de la grille\footnotemark[1] ;
\item comme c'est le cas dans la plupart des grilles de mots croisés, si $l_{G}$ (respectivement $h_{G}$) est suffisamment petit\footnotemark[1]\footnotetext[1]{Ces valeurs seront définies dans une section ultérieure.}, on imposera que la première ligne (respectivement la première colonne) ne contienne pas de case noire ;
\item il ne peut pas y avoir deux cases noires adjacentes. Cette contrainte permettra entre autres d'obtenir une certaine variété dans la longueur des mots.
\end{itemize}

\paragraph{N.B.} Les cases noires seront placées automatiquement par le programme. Eventuellement, on pourra prévoir que l'utilisateur, s'il le désire, puisse placer lui-même les cases noires.

\bigskip
\subsection{Outils}
Nous disposons pour ce projet d'outils de programmation et de modélisation courants. Nous disposons en outre d'une liste de mots officielle du scrabble (ODS, version 5, août 2007), disponible à l'adresse \url{http://www.3zsoftware.com/fr/wordmagic/listes.php}. Il s'agit d'une liste de mots de 2 à 15 lettres, sans accents, triés par ordre alphabétique. Pour un intérêt pratique, nous l'avons décomposé en 14 fichiers contenant chacun la liste des mots d'une même longueur, classés par ordre alphabétique. De plus, ils sont écrits en majuscule (pour plus de lisibilité), et chaque lettre est séparée par un espace (permet d'utiliser des fonctions de tri plus facilement pour des lettres en milieu de mot).

\clearpage
\section{Spécifications techniques}
\subsection{Diagramme des cas d'utilisation}
\begin{figure}[H]
 \centering
 \includegraphics[width=0.95\textwidth]{./img/usecase.png}
 \label{fig:usecase}
\caption{Diagramme des cas d'utilisation}
\end{figure}

Comme nous l'avons expliqué plus haut, on prévoira deux cas d'utilisations principaux : celle en tant que créateur de grille et celle en tant que joueur.

\subsection{Diagrammes d'activité}
\begin{figure}[H]
 \centering
 \includegraphics[width=0.8\textwidth]{./img/activite_generer.png}
 \label{fig:act_gen}
\caption{Diagramme de l'activité \og{} générer une grille \fg{}}
\end{figure}

\begin{figure}[H]
 \centering
 \includegraphics[width=0.8\textwidth]{./img/activite_jeu.png}
 \label{fig:act_jeu}
\caption{Diagramme de l'activité \og{} jouer \fg{}}
\end{figure}

\subsection{Diagrammes de séquence}
\begin{figure}[H]
 \centering
 \includegraphics[width=0.7\textwidth]{./img/init.png}
 \label{fig:seq_init}
\caption{Diagramme de séquence du scénario \og{} initialiser la grille \fg{}}
\end{figure}

\begin{figure}[H]
 \centering
 \includegraphics[width=0.75\textwidth]{./img/minPoss.png}
 \label{fig:seq_minPoss}
\caption{Diagramme de séquence du scénario \og{} calcul du minimum des possibilités \fg{}}
\end{figure}

\clearpage
\begin{figure}[H]
 \centering
 \includegraphics[width=0.99\textwidth]{./img/ajouterMot.png}
 \label{fig:seq_ajMot}
\caption{Diagramme de séquence du scénario \og{} ajouter un mot \fg{}}
\end{figure}

\begin{figure}[H]
 \centering
 \includegraphics[width=0.75\textwidth]{./img/affichage.png}
 \label{fig:seq_aff}
\caption{Diagramme de séquence du scénario \og{} afficher la grille \fg{}}
\end{figure}

\clearpage
\subsection{Diagramme de classes}
\begin{figure}[H]
 \includegraphics[width=\textwidth]{./img/classdiagram2.png}
 \label{fig:classes}
\caption{Diagramme de classes}
\end{figure}

\newpage
\section{Test unitaires}

\subsection{Utilisation du framework \emph{CPPUNIT}}
La création et l'exécution de tests unitaires peut \^etre fastidieuse. C'est pourquoi \emph{CPPUNIT} a été créé. Il permet d'implémenter de manière pratique ses tests unitaires, de former des batteries de tests auxquelles il sera facile de faire appel. Ces ensemble de tests auront une sortie permettant de voir aisément quels tests ont réussi, lesquels ont échoué où et pourquoi, de la m\^eme manière que le compilateur indique à quelles lignes se trouvent les erreurs lorsqu'il y en a. 

Nous avons groupé les tests par les classes les concernant. Chacune des classes de tests est nommée \emph{[Nom de la classe]Test}. Nous vous y renvoyons afin de voir l'illustration des quelques explications données ici.

\subsubsection*{Les classes de tests}
\emph{CPPUNIT} met à notre disposition la classe \emph{TestFixture} qui est une sorte de conteneur de tests permettant la création de l'environnement nécessaire à une série de test. Les méthodes \emph{setUp} et \emph{tearDown} permettent, une fois redéfinis par les soins de l'utilisateur, la mise en place de l'environnement et le nettoyage de la mémoire.

Le framework met également à disposition un certain nombre de macros facilitant son utilisation (dans le fichier d'en-t\^ete \emph{cppunit/extensions/HelperMacros.h} que l'on peut inclure). Ainsi on peut écrire par exemple les instructions suivantes :

\begin{verbatim}
    CPPUNIT_TEST_SUITE (GrilleMotsCroisesTest);
    CPPUNIT_TEST (chargerTest);
    CPPUNIT_TEST (estRemplieTest);
    CPPUNIT_TEST (estRemplieMotsTest);
    CPPUNIT_TEST (ajouterCaseNoireTest);
    CPPUNIT_TEST (verifieContraintesTest);
    CPPUNIT_TEST (defMotsTest);
    CPPUNIT_TEST (initCasesNoiresTest);
    //CPPUNIT_TEST (initTest);
    CPPUNIT_TEST_SUITE_END ();
\end{verbatim}

Ces lignes permettent la mise en place d'une suite de tests. En argument des macros \emph{CPPUNIT\_TEST} se trouvent les noms des fonctions de tests qui seront définies par l'utilisateur.
\bigskip

Enfin, lors de l'écriture des fonctions de tests, d'autres macros permettent de faciliter encore le travail du testeur. \emph{CPPUNIT} possède des macros permettant de faire des assertions, telles que \emph{CPPUNIT\_ASSERT}, \emph{CPPUNIT\_ASSERT\_EQUAL} ou encore \emph{CPPUNIT\_ASSERT\_THROW}. La macro \emph{CPPUNIT\_ASSERT}, la plus basique, prend en argument une expression renvoyant un booléen. Si cette expression est vraie, alors le test sera réussi. Les autres macros fonctionnent sur le m\^eme modèle, l'une permettant de tester l'égaliter de 2 arguments, tandis que l'autre permet de savoir si une fonction a bien lancé l'exception à laquelle on doit s'attendre.

\subsubsection*{Le programme de test}
Après avoir créé la classe de test, nous avons besoin d'un programme principal pour les exécuter. Ce programme va utiliser une instance de la classe \emph{TestResult} comme un gestionnaire de la procédure de test. Les objets de cette classes informent les différents \emph{listeners} des autres classes à propos des résultats de tests, de leur progression, etc. Dans notre programme de test l'objet de la classe \emph{TestResult} communique avec les instances des classes \emph{TestResultCollector} et \emph{BriefTestProgressListener}. Le lancement des tests est ensuite assuré par la méthode \emph{run} du \emph{TestRunner}.

Enfin, les résultats des tests nous sont restitués sous la forme de messages ressemblant à ceux d'un compilateur. Ce travail est effectué par l'instance de la classe \emph{CompilerOutputter}. Nous vous renvoyons au fichier \emph{mainTest.cpp} pour l'illustration de ces dernières lignes.
\bigskip

Voici à présent les exemples de tests unitaires que nous avons menés à l'aide de \emph{CPPUNIT}.

%\subsection{Méthodes de la classe \emph{CaseMotsCroises}}

\subsection{Méthodes de la classe \emph{Mot}}
\subsubsection*{contient(int x, int y)}
 \begin{itemize}
  \item \textbf{Cas usuel : } on teste une case appartenant au mot.
  \item \textbf{Cas limite : } la case n'appartient pas au mot.
 \end{itemize}
 
 \subsubsection*{estRempli()}
 \begin{itemize}
  \item \textbf{Cas usuel : } on teste un mot ni vide ni plein.
  \item \textbf{Cas limite : } le mot est entièrement vide ou entièrement plein.
 \end{itemize}

\subsection{Méthode de la classe \emph{GrilleMotsCroises}}

\subsubsection*{charger()}
 \begin{itemize}
  \item \textbf{Cas usuel : } on charge une grille sauvegardée existante.
  \item \textbf{Cas d'erreur : } on tente de charger une grille dont le fichier de sauvegarde n'existe pas.
 \end{itemize}
 
\subsubsection*{estRemplie()}
    \begin{itemize}
\item\textbf{Cas limite : } la grille est entièrement vide ou entièrement pleine.
\item\textbf{Cas usuel : }  la grille n'est ni vide ni pleine.
\end{itemize}

\subsubsection*{estRemplieMots()}
    \begin{itemize}
\item\textbf{Cas limite : } la grille est entièrement vide ou entièrement pleine.
\item\textbf{Cas usuel : }  la grille n'est ni vide ni pleine.
\end{itemize}

\subsubsection*{ajouterCaseNoire(x:int, y:int)}
    \begin{itemize}
    \item\textbf{Cas limite : } on ajoute une case sur une case déjà noire. On ajoute une case noire sur les bords du tableau.
    \item \textbf{Cas usuel : } on ajoute une case noire.
\end{itemize}

\subsubsection*{init()}
    \begin{itemize}
\item \textbf{Cas limite : } 
\begin{itemize}
	\item[] Grille $5\times 5$
\item[] Grille $50\times 50$
\item[] Pourcentage $< 8 \%$
\end{itemize}
\item \textbf{Cas usuel : } entre les deux limites et pourcentage $ \geq 8\%$.
\end{itemize}

\subsubsection*{verifieContraintes(int x, int y)}
    \begin{itemize}
\item \textbf{Cas usuel : } on teste une case noire ou une case voisine d'une case noire.
\item \textbf{Cas limite : } on teste des situations au bord du tableau.
\end{itemize}

\subsubsection*{defMots(int lg, int haut)}
\begin{itemize}
 \item \textbf{Cas usuel : } la grille n'est ni vide ni pleine de cases noires.
 \item \textbf{Cas limite : } la grille est entièrement remplie ou vide de cases noires.
\end{itemize}

\subsubsection*{initCasesNoires(int lg, int haut)}
\begin{itemize}
 \item \textbf{Cas usuel : } la grille a ses 2 dimensions inférieures à 15.
 \item \textbf{Cas limite : } la grille a une seule dimension inférieure à 15.
\end{itemize}



\newpage
\section{Présentation du programme}
\subsection{Ce que peut faire l'utilisateur}

Lorsqu'un utilisateur lance l'application créé, celui-ci à 4 choix :

\begin{itemize}
\item générer une grille de mots croisés ;
\item éditer une grille existante ;
\item jouer ;
\item quitter le jeu. 
\end{itemize}

\subsubsection{Cas où l'utilisateur veut générer une grille}

Il lui sera alors demandé de nous fournir certaines contraintes à partir desquelles l'application
tentera de générer une grille. Ces contraintes sont :
\begin{itemize}
\item La hauteur de la grille ; 
\item la largeur de la grille ;
\item le pourcentage de cases noires que doit contenir notre grille. 
\end{itemize}

Le programme commence alors par proposer une grille avec uniquement les cases noires à l'utilisateur.
S'il le souhaite, l'utilisateur peut demander au programme de lui proposer une autre grille sous les m\^eme contraintes.
\newline
Une fois la grille à remplir choisie, l'utilisateur ne peut plus rien faire jusqu'à ce que la génération soit terminée (qu'elle soit un succès ou un échec). Si la génération à réussie, on lui proposera d'éditer les définitions des mots présents dans la grille, et s'il souhaite sauver la grille générée (avec les définitions éditées le cas échéant).

Une fois tout cela effectué, le programme revient au menu initial où l'on peut choisir d'effectuer une autre action.

\subsubsection{Cas où l'utilisateur veut éditer une grille existante}

Lorsque l'utilisateur choisit d'éditer une grille, l'application lui fournit une liste 
des grilles de mots croisés existantes.

Une fois la grille choisie, le programme  affiche tous les mots présents avec leur définition. L'utilisateur peut alors choisir d'éditer les définitions de différents mots (qu'une défintion existe ou non).
Lorsqu'il a fini d'éditer, il peut sauvegarder la grille avec ses définitions (il peut changer le nom de la grille).

Puis l'utilisateur retourne au menu initial.

\subsubsection{Cas où l'utilisateur veut jouer}

Comme précédemment, il lui est demandé de choisir une grille de mots croisés (de préférence avec des définitions car c'est plus intéressant).

Une grille contenant uniquement des cases noires ou vides lui est alors proposée. Il ne lui reste plus qu'à jouer.

Il peut alors : 
\begin{itemize}
 \item Placer une lettre dans la grille ;
 \item placer un mot entier ;
 \item enlever une lettre ;
 \item faire vérifier les mots déjà posés ;
 \item voir la solution.
\end{itemize}

\subsection{Fonctionnnement de la génération d'une grille}

\subsubsection{Generation des cases noires}

%Parler du remplissage des listes de mots%
Le programme commence par placer aléatoirement des cases noires dans la grille. Si la hauteur est inférieure à 15, la première colonne ne doit pas contenir de case noir. Il en est de même pour la la première ligne (si la longueur est inférieure à 15). Pour chaque case noire, on prend soin de bien vérifier qu'il n'existe pas une case noire déjà définie dans une case adjacente, auquel cas on choisit un autre emplacement. On vérifie également que l'emplacement choisi ne crée pas une case vide <<isolée>>, c'est-à-dire une configuration du type

{\centering
\begin{minipage}{0.25\linewidth}
\begin{small}\begin{verbatim}
-------------
|   |###|   |
-------------
|###|   |###|
-------------
|   |###|   |
-------------
\end{verbatim}\end{small}
\end{minipage}\par}

\bigskip
Une fois les cases noires générées, d'autres vérifications doivent être effectuées. En effet, il est indispensable de vérifier qu'il n'existe pas d'<<espace libre>> (on appelle \textit{espace libre} une succession de cases vides sur une ligne ou sur une colonne) de plus de 15 cases, puisque nous ne disposons que de mots de longueur inférieure ou égale à 15.

De plus, on vérifie que sur deux colonnes ou deux lignes successives, il n'existe pas deux espaces libres coïncidant sur plus de 10 cases. Cela simplifiera la tâche des fonctions de filtrage lors du remplissage de la grille. Si l'on se trouve dans l'une ou l'autre de ces configurations, on ajoutera une case noire au milieu de l'espace libre (celui de plus de 15 cases dans le premier cas, dans un des deux espaces vides examinés dans le second cas).

Afin de respecter la proportion imposée par l'utilisateur, on va chercher une case noire présente dans la grille dont la suppression entraîne la création d'un espace vide de longueur minimum (et toujours inférieure ou égale à 15) en ligne et en colonne. Si on peut en trouver une, on  la supprime. Sinon, la proportion est donc augmentée.

\subsubsection{Remplissage de la grille}

Une fois les cases noires posées, il ne nous reste plus qu'à remplir la grille. La première chose à faire est de filtrer les possibilités pour chaque Mot de la grille.

\subsubsection*{Fonctionnement du filtrage}
Lorsque deux Mots se croisent sur la grille on regarde à leur croisement quelles sont les lettres possibles.

\paragraph{Exemple} La première case d'un mot de deux lettres croise la premiere case d'un mot de 15 lettres. On sait que pour les mots de deux lettres il n'existe pas de mots commençant par les lettres Q, Y, Z. On sait aussi que pour les mots de 15 lettres il n'existe pas de mots commençant par la lettre X. Par conséquent, on va enlever des listes de possibilités des deux Mots tous les mots commençant par les lettres Q, X, Y, Z. On a ainsi appliqué un filtre à la case ou se croisait ces deux Mots.

\bigskip
Lorsqu'on effectue un filtrage, on parcourt une première fois toutes les cases non noires de la grille en filtrant lorsque deux mots se croisent, puis tant qu'au cours d'un parcours de la grille on a éliminé au moins une possibilité (et qu'il reste au moins une possibilité pour chaque Mot),on recommence à la parcourir.
\newline
Une fois le filtrage effectué, on va alors avoir plusieurs possibilités qui s'offrent à nous. On peut ainsi :
\begin{itemize}
 \item choisir un Mot pour lequel on choisira aléatoirement une des possibilités parmis celles encore possibles
 \item enlever un Mot
 \item choisir un Mot pour lequel on choisira la ``meilleure'' possibilité restante
 \item enlever deux Mots.
\end{itemize}

\subsubsection*{Choisir le Mot et le remplir aléatoirement}

S'il reste une possibilité pour chaque Mot en fin de filtrage, on va devoir choisir le Mot à remplir. Notre outil de décision va \^etre une fonction  qui prend en compte le nombre de lettres  et le nombre de mots possibles pour chaque Mots.

Une fois le mot choisit, on va le remplir aléatoirement avec un mot de sa liste des possibilités. 

\subsubsection*{Enlever un mot}
On choisit d'enlever un mot de la grille s'il ne reste plus de possibilités pour au moins un mot. Pour savoir quel est le meilleur mot à enlever, on va tour à tour simuler la suppression de chaque mot déjà rempli de la grille. Cette simulation est plut\^ot longue étant donné que pour tous les mots non  remplis on réinitialise la liste des possibilités puis on applique les fonctions de filtrage (qui  prennent en compte les mots déjà placés). En fin de compte, on enlèvera le mot qui nous laisse le plus de possibilités au coup suivant.

\subsubsection*{Choisir un Mot et le remplir avec la meilleure possibilité}

Lorsqu'au coup d'avant on a enlever un mot et qu'on peut à se coup placer un mot, on va choisir avec la m\^eme fonction de décision que précédemment le mot à remplir. Par contre, contrairement à d'habitude, si le nombre de mots parmi lesquels on a le choix est inférieur à un certain seuil fixé arbitrairement (actuellement 500), on va tester tous les mots avec la grille actuelle et placer celui qui nous laisse le plus de chance de finir la grille. Si le nombre de mots parmi lesquels on a le choix est supérieur au seuil, on fait un choix aléatoire.

\subsubsection*{Enlever deux Mots d'un coup}

Si au coup d'avant on a rempli un Mot avec celui laissant le maximum de possibilités, et que l'on ne peut plus en poser (au moins un Mot n'a plus de possibilité suite au filtrage), on va enlever deux Mots d'un coup en appliquant la méthode pour enlever un mot deux fois de suite.

\newpage
\subsection{Format de sauvegarde des grilles}
Les grilles sont sauvegardées sous la forme XML, grâce aux fonctions et aux structures proposées par les librairies \textit{tinyxml}. La structure générale est la suivante

\bigskip
\begin{lstlisting}[language=xml, basicstyle=\scriptsize]
<Grille>
    <Details hauteur="10" longueur="10" nbCasesNoires="8" nbMotsH="16" nbMotsV="16" />
    <Contenu>
        <Mot ligne="0" colonne="0" vertical="0">
            <Libelle>MOT1</Libelle>
            <Definition>DEF1</Definition>
        </Mot>
        <Mot ligne="1" colonne="0" vertical="0">
            <Libelle>MOT2</Libelle>
            <Definition>DEF2</Definition>
        </Mot>
		</Contenu>
		etc...
</Grille>
\end{lstlisting}

\newpage
\subsection{Exemples de grilles générées avec notre programme}
\fvset{samepage=true,fontsize=\small}
Voici quelques exemples des grilles que nous avons pu générer grâce à notre programme. Nous avons généré des grilles $5\times 5$ ou $6\times 6$ sans case noire (cas extrêmes), des grilles $20 \times 20$ avec $18\%$ de cases noires, des grilles $10 \times 10$ avec $10\%$ de cases noires (ce qui est un très bon pourcentage pour une grille de mots croisés). On peut donc dire que l'objectif global a été atteint. Cependant, nous n'avons pas pu générer de grilles $50\times 50$, même en augmentant à $20\%$ la proportion de cases noires.

\subsubsection{Grilles $6 \times 6$ sans case noire}

\bigskip
{\centering
\begin{minipage}{0.5\linewidth}
 \VerbatimInput{./res/660.txt}

\bigskip
\VerbatimInput{./res/symetric.txt}
\end{minipage}
\par}

\bigskip
Remarquons que cette dernière grille est symétrique !!

\subsubsection{Grille $10 \times 10$ avec $10\%$ de cases noires}

\bigskip
{\centering
\begin{minipage}{0.5\linewidth}
 \VerbatimInput{./res/10-10-10.txt}
\end{minipage}
\par}

\subsubsection{Grille $20 \times 20$ avec $18\%$ de cases noires}

\bigskip
 \VerbatimInput[fontsize=\footnotesize]{./res/20-20-18.txt}

\newpage
\subsubsection*{Grille $45 \times 30$ avec $25\%$ de cases noires}
\VerbatimInput[fontsize=\tiny]{./res/45-30-25.txt}

\newpage
\section*{Conclusion}
\addcontentsline{toc}{section}{Conclusion}
\end{document}
